// 给定一副牌，每张牌上都写着一个整数。

// 此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：

// 每组都有 X 张牌。
// 组内所有的牌上都写着相同的整数。
// 仅当你可选的 X >= 2 时返回 true。

//  

// 示例 1：

// 输入：[1,2,3,4,4,3,2,1]
// 输出：true
// 解释：可行的分组是 [1,1]，[2,2]，[3,3]，[4,4]
// 示例 2：

// 输入：[1,1,1,2,2,2,3,3]
// 输出：false
// 解释：没有满足要求的分组。
// 示例 3：

// 输入：[1]
// 输出：false
// 解释：没有满足要求的分组。
// 示例 4：

// 输入：[1,1]
// 输出：true
// 解释：可行的分组是 [1,1]
// 示例 5：

// 输入：[1,1,2,2,2,2]
// 输出：true
// 解释：可行的分组是 [1,1]，[2,2]，[2,2]

// 提示：

// 1 <= deck.length <= 10000
// 0 <= deck[i] < 10000

#include <vector>
#include <unordered_map>
#include <algorithm>
#include <iostream>

using namespace std;

class Solution1 {
public:
    bool hasGroupsSizeX(vector<int>& deck) {
        unordered_map<int, int> hash{}; // 数字对应出现的次数
        for (auto i : deck) {
            ++hash[i];
        }
        vector<int> nums{}; // 所有数字出现的次数
        for (auto it : hash) {
            nums.push_back(it.second);
        }
        sort(nums.begin(), nums.end());
        if (nums[0] < 2) return false;
        for (int i{2}; i <= nums[0]; ++i) { // 尝试小于最小个数的每一个数字
            bool success = true;
            for (auto num : nums) {
                if (num % i != 0) {
                    success = false;
                    break;
                }
            }
            if (success) {
                return true;
            }
        }
        return false;
    }
};

// 最大公约数
class Solution {
public:
    bool hasGroupsSizeX(vector<int>& deck) {
        unordered_map<int, int> cardCnt{};
        for (int card : deck) ++cardCnt[card];
        int res{0};
        for (auto &a : cardCnt) {
            res = gcd(a.second, res); // 求所有的最大公约数
        }
        return res > 1;
    }
    // 求最大公约数
    int gcd(int a, int b) {
        return a == 0 ? b : gcd(b % a, a);
    }
};

int main() {
    Solution s;
    vector vec{1,1,1,2,2,2,3,3};
    cout << s.hasGroupsSizeX(vec) << endl;
    return 0;
}